#include <bits/stdc++.h>
using namespace std;

/*
440. 字典序的第K小数字
已解答
困难
相关标签
premium lock icon
相关企业
给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。

 

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
示例 2:

输入: n = 1, k = 1
输出: 1
 

提示:

1 <= k <= n <= 109
*/

// 法一
class Solution {
public:
    int findKthNumber(int n, int k) {
        int cur = 1; // 当前检查的数字，从1开始
        k--; // 初始化为k-1，因为第一个数字1已经算作第1个
        while (k > 0) {
            // 计算以cur为前缀的数字总数（即子树节点数）
            int steps = countSteps(cur, n);
            if (steps <= k) {
                // 如果总数<=k，说明第k个数不在当前前缀的子树中
                // 跳过整个子树，cur右移（如1→2）
                k -= steps;
                cur++;
            } else {
                // 否则第k个数在当前前缀的子树中
                // 进入下一层（如1→10），k减1（因为cur本身消耗一个位置）
                cur *= 10;
                k--;
            }
        }
        return cur; // 当k减到0时，cur即为所求
    }

    // 计算以cur为前缀且不超过n的数字总数
    int countSteps(long cur, long n) {
        int steps = 0;
        long first = cur;  // 当前层的最小值（如cur=1时，第一层1，第二层10）
        long last = cur;   // 当前层的最大值（如cur=1时，第一层1，第二层19）
        while (first <= n) {
            // 当前层的有效节点数 = min(last,n) - first + 1
            // 例如n=13, cur=1时：
            // 第一层[1] → 1个
            // 第二层[10,11,12,13] → 4个（last=19但n=13）
            steps += min(last, n) - first + 1;
            first *= 10;    // 下一层的最小值
            last = last * 10 + 9; // 下一层的最大值
        }
        return steps;
    }
};

// 更完整的梳理
class Solution {
public:
    /**
     * @brief 在字典序排列的数字中找到第k小的数字
     * @param n 数字范围上限 [1, n]
     * @param k 目标位置（1-based）
     * @return 第k小的数字
     * 
     * 算法思路：
     * 1. 将数字视为十叉树，按前序遍历顺序（字典序）查找
     * 2. 通过计算子树大小决定跳过或进入子树
     * 时间复杂度：O((log_{10}n)^2)
     */
    int findKthNumber(int n, int k) {
        long long curr = 1;  // 当前检查的数字（使用long long防止溢出）
        k--;                 // 转换为0-based索引（第一个数字1已默认处理）

        while (k > 0) {
            // 计算以curr为前缀的数字总数（子树大小）
            int subtreeSize = countSubtreeNodes(curr, n);
            
            if (subtreeSize <= k) {
                // 目标不在当前前缀的子树中：跳过整个子树
                k -= subtreeSize;
                curr++;      // 移动到下一个前缀（如1→2）
            } else {
                // 目标在当前前缀的子树中：进入下一层
                curr *= 10;  // 进入子节点（如1→10）
                k--;         // 消耗当前节点（如1→10时，1已算作一个数字）
            }
        }
        return static_cast<int>(curr);
    }

private:
    /**
     * @brief 计算以prefix为前缀且不超过n的数字数量
     * @param prefix 当前数字前缀
     * @param n 数字范围上限
     * @return 子树节点数
     * 
     * 示例：prefix=1, n=13 → 子树包含1,10,11,12,13 → 返回5
     */
    int countSubtreeNodes(long long prefix, long long n) {
        int count = 0;
        long long first = prefix;  // 当前层最小值（如prefix=1时，第一层1，第二层10）
        long long last = prefix;   // 当前层最大值（如prefix=1时，第一层1，第二层19）

        while (first <= n) {
            // 当前层有效节点数 = min(last,n) - first + 1
            count += min(last, n) - first + 1;
            
            // 进入下一层
            first *= 10;          // 下一层最小值（如10→100）
            last = last * 10 + 9; // 下一层最大值（如19→199）
        }
        return count;
    }
};